package com.hainiu.cat.sort;

/**
 * create by biji.zhao on 2021/5/29
 */
public class FastSort {

    public static void main(String[] args) {
//        testSortFast();
        int[] a = {1, 3, 6, 8, 9, 10, 20, 34, 38, 39, 47, 99};
        System.out.println(find(a, 0, a.length - 1, 99));
    }

    /**
     * 二分查找法
     * @param nums  数组
     * @param start 开始位置
     * @param end   结束位置
     * @param key   查找的元素
     * @return    所在下标
     */
    private static int find(int[] nums, int start, int end, int key) {
        int mid = (end - start) / 2 + start;
        if (nums[mid] == key) {
            return mid;
        }
        if (start >= end) {
            return -1;
        }
        if (nums[mid] > key) {
            return find(nums, start, mid -1, key);
        }
        if (nums[mid] < key) {
            return find(nums, mid + 1, end, key);
        }
        return -1;
    }

    private static void testSortFast() {
        int[] a = {3, 5, 2, 9,73,1, 10, 37, 2};
        System.out.println(arrayToString(a));
        fastSort(a, 0, a.length - 1);
        System.out.println(arrayToString(a));
    }

    /**
     * 快速排序法
     * @param nums  数组
     * @param left  开始位置
     * @param right 结束位置
     */
    private static void fastSort(int[] nums, int left, int right) {
        if (nums.length == 0 || left >= right) {
            return ;
        }
        int key = nums[left];
        int i = left;
        int j = right;
        while (i < j) {
            // 从右往左找到比他小的，切记不能使 j < i
            while (nums[j] >= key && i < j) {
                j--;
            }
            // 从左往右找到第一个比他大的，切记不能 i > j
            while (nums[i] <= key && i < j) {
                i++;
            }
            if (i < j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        nums[left] = nums[i];
        nums[i] = key;
        fastSort(nums, left, i - 1);
        fastSort(nums, i + 1, right);
    }

    public static String arrayToString(int[] nums) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < nums.length; i++) {
            if (i < nums.length - 1) {
                builder.append(nums[i]).append(",");
            }else {
                builder.append(nums[i]);
            }
        }
        return builder.toString();
    }
}
